This invention is a variant of 2w-ary point multiplication with resistance against side-channel attacks that avoids a fixed table without requiring frequently repeated projective randomisation.
An additional advantage of the new method is that it is easily parallelizable on two-processor systems. One essential change in strategy compared with earlier methods for side-channel attack resistant point multiplication is the use of a right-to-left method (the scalar is processed starting at the least significant digit, cf. [15]) whereas the conventional methods work in a left-to-right fashion.
The method works in three stages, which are called initialisation stage, right-to-left stage, and result stage.
First there will be a high-level view of these stages before they are discussed in detail.
The method for computing eP is parameterized by an integer w≧2 and a digit set B consisting of 2w integers of small absolute value such that every positive scalar e can be represented in the form
  e  =            ∑              0        ≤        i        ≤        l                                  ⁢                  ⁢                  b        i            ⁢              2        wi            using digits b1 εB; for exampleB={0,1, . . . , 2w−1}orB={−ww-1, . . .,2w-1−1}
A representation of e using the latter digit set can be easily determined on the fly when scanning the binary digits of e in right-to-left direction.
If e is at most n bits long (i.e. 0<e<2n), l=└n/w┘ is sufficient.
Let B′ denote the set {|b| |bεB} of absolute values of digits, which has at least 2{w−1}+1 and at most 2w elements. The point multiplication method uses #(B′)+1 variables for storing points on the elliptic curve in projective representation: Namely, one variable Ab for each bεB′, and one additional variable Q.
Let Abinit denote the value of Ab at the end of the initialisation stage, and let Absum denote the value of Ab at the end of the right-to-left stage. The initialisation stage sets up the variables Ab(bεB′) in a randomized way such that Abinit ≠0 for each b, but
            ∑              b        ∈                  B          ′                                          ⁢                  ⁢          b      ⁢                          ⁢              A        b        init              =  0(O denotes the point at infinity, the neutral element of the elliptic curve group.)
Then the right-to-left stage performs computations depending on P and the digits b1, yielding new values Absum of the variables Ab satisfying
      A    b    sum    =            A      b      init        +                  ∑                              0            ≤            i            ≤            l                                              b              i                        =            b                                                        ⁢                          ⁢                        2          wi                ⁢        P              -                  ∑                              0            ≤            i            ≤            l                                              b              i                        =                          -              b                                                                    ⁢                          ⁢                        2          wi                ⁢        P            for each bεB′. Finally, the result stage computes
            ∑              b        ∈                              B            ′                    -                      {            0            }                                                    ⁢                  ⁢          b      ⁢                          ⁢              A        b        sum              ,which yields the final result eP because
                                          ∑                          b              ∈                                                B                  ′                                -                                  {                  0                  }                                                                                                    ⁢                                          ⁢                      b            ⁢                                                  ⁢                          A              b              sum                                      =                ⁢                                                            ∑                                  b                  ∈                                                            B                      ′                                        -                                          {                      0                      }                                                                                                                                    ⁢                                                          ⁢                              b                ⁢                                                                  ⁢                                  A                  b                  init                                                                    ︸              0                                +                                                ⁢                              ∑                          b              ∈                                                B                  ′                                -                                  {                  0                  }                                                                                                    ⁢                      b            (                                                            ∑                                                            0                      ≤                      i                      ≤                      l                                                                                      b                        i                                            =                      b                                                                                                                              ⁢                                                                  ⁢                                                      2                    wi                                    ⁢                  P                                            -                                                ∑                                                            0                      ≤                      i                      ≤                      l                                                                                      b                        i                                            =                                              -                        b                                                                                                                                                    ⁢                                                                  ⁢                                                      2                    wi                                    ⁢                  P                                                      )                                                  =                ⁢                                            ∑                              0                ≤                i                ≤                l                                                                                  ⁢                                                  ⁢                                          b                i                            ⁢                              2                wi                            ⁢              P                                =                      eP            .                              
The point multiplication method is a signed-digit variant of Yao's right-to-left method [15] (see also [16, exercise 4.6.3-9]) and [17, exercise 4.6.3-9]) and [18]) with two essential modifications for achieving resistance against side-channel attacks: The randomized initialisation stage is different; and in the right-to-left stage, the digit 0 is treated like any other digit.